#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2020年03月06日
版    本：v1.0.0
描    述：
Copyright (C) 2020 All rights reserved.
'''

import Queue

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


class Solution(object):
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """

        dic = dict()
        q = Queue.Queue()
        q.put(root)

        while not q.empty():
            count = q.qsize()
            while count > 0:
                p = q.get()
                if dic.get(k - p.val, None):
                    return True
                dic[p.val] = True

                if p.left:
                    q.put(p.left)
                if p.right:
                    q.put(p.right)
                count -= 1

        return False


class Solution(object):
    def __init__(self):
        self.dic = dict()
        
    def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        self.dic[root.val] = True
        return self.dfs(root.left, k) or self.dfs(root.right, k)

    def dfs(self, root, k):
        if not root:
            return False

        if self.dic.get(k-root.val, None):
            return True

        self.dic[root.val] = True
        return self.dfs(root.left, k) or self.dfs(root.right, k)